import bean.TreeNode;

public class LeetCode437 {
    public static void main(String[] args) {
//        TreeNode node = new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3, null, new TreeNode(4, null, new TreeNode(5)))));
        TreeNode node = new TreeNode(100, new TreeNode(1000000000, new TreeNode(1000000000, new TreeNode(1000000000, new TreeNode(1000000000, new TreeNode(1100000000), null),null) ,null) ,null), null);
        System.out.println(new LeetCode437().pathSum(node, 0));
    }

    int result = 0;
    /**
     * 思路，每个节点都重新作为根节点，计算当前根节点到某个子节点的和是否等于targetSum
     * @param root
     * @param targetSum
     * @return
     */
    public int pathSum(TreeNode root, int targetSum) {

        if (root == null){
            return 0;
        }

        int sum = root.val;
        if (sum == targetSum){
            result++;
        }
        dfs(root.left, sum, targetSum);
        dfs(root.right, sum, targetSum);



        pathSum(root.left,  targetSum);
        pathSum(root.right,  targetSum);
        return result;
    }

    public void dfs(TreeNode root,int sum, int targetSum){
        if (root == null){
            return;
        }

        sum += root.val;

        if (sum == targetSum){
            result++;
        }

            dfs(root.left, sum, targetSum);
            dfs(root.right, sum, targetSum);

    }
}
